package br.usp.wta.inductor;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import br.usp.language.automata.StackMachine;
import br.usp.language.automata.State;
import br.usp.language.automata.StateMachine;
import br.usp.language.automata.Transition;
import br.usp.language.syntax.grammar.ContextFreeGrammar;
import br.usp.language.syntax.grammar.Epsilon;
import br.usp.language.syntax.grammar.NonTerminal;
import br.usp.language.syntax.grammar.ProductionElement;
import br.usp.language.syntax.grammar.ProductionRule;
import br.usp.language.syntax.grammar.Terminal;

public class Ivone {

    List<Transition> visitedTransition = new ArrayList<Transition>();

    /**
     * Infere APE a partir de automato finito
     * 
     * @param sm
     * @return
     */
    public ContextFreeGrammar inferAPE(StateMachine sm) {

        // n = number of submachines
        int n = 0;

        // 1. Encontrar caminhos minimos do Estado Inicial ao Final
        State initialState = sm.getInitialState();
        State finalState = null;

        List<State> visitedStates = new ArrayList<State>();

        // TODO: inverter lista pra melhorar desempenho
        for (State state : sm.getAllStates()) {
            if (state.isAcceptState()) {
                finalState = state;
                break;
            }
        }

        List<List<Transition>> minPaths = this.findMinPaths(sm, initialState, finalState);
        System.out.println("Caminhos minimos: " + minPaths);

        // 2. Estes caminhos são as primeiras produções da gramática livre de contexto
        ContextFreeGrammar grammar = new ContextFreeGrammar();
        NonTerminal nTinitial = new NonTerminal("S" + n++);
        grammar.addNonTerminal(nTinitial);
        grammar.setStartSymbol(nTinitial);

        for (List<Transition> minPath : minPaths) {
            if (visitedTransition.containsAll(sm.getAllTransitions())) {
                break;
            }
            ProductionRule rule = this.createNewRule(grammar, nTinitial, minPath);
            visitedTransition.addAll(minPath);
            // 3. Para cada CMink, verificar se existe um caminho a partir dos estados do caminho
            // mínimo que retorne ao caminho CMink.

            n = findNewCycles(sm, visitedStates, n, grammar, minPath, rule);
        }

        // TODO deletar
        for (ProductionRule r : grammar.getRules()) {
            System.out.println(r);
        }

        return grammar;
    }

    /**
     * @param sm
     * @param n
     * @param grammar
     * @param currentPath
     * @param rule
     * @return
     */
    protected int findNewCycles(StateMachine sm, List<State> visitedStates, int n, ContextFreeGrammar grammar,
            List<Transition> currentPath, ProductionRule rule) {

        List<State> statesInPath = new ArrayList<State>();
        statesInPath.add(currentPath.get(0).getStateFrom());
        for (Transition t : currentPath) {
            statesInPath.add(t.getStateTo());
        }
        List<Transition> transFrom = new ArrayList<Transition>();
        for (State state : statesInPath) {
            transFrom.addAll(state.getAllTransitions());
        }
        List<Transition> cycle;
        do {
            // TODO deletar
            System.out.println("Analisando Caminho Minimo:");
            System.out.println(statesInPath);

            cycle = this.findMinimalCycle(sm, statesInPath, visitedStates);
            //visitedStates.addAll(statesInPath);

            System.out.println("Ciclo: " + cycle);

            if (!cycle.isEmpty()) {
                int callerIndex = statesInPath.indexOf(cycle.get(0).getStateFrom());
                int targetIndex = statesInPath.indexOf(cycle.get(cycle.size() - 1).getStateTo());

                visitedTransition.addAll(cycle);
                // Verifica se já existe uma submáquina que represente Ck
                ProductionRule existentRule = getRule(grammar, cycle);
                if (existentRule != null) { // Ja existe regra igual a essa
                    this.insertSubMachineCall(grammar, rule, callerIndex, targetIndex, existentRule.getGenerator());
                } else {
                    // Uma nova submáquina (n+1) é criada
                    NonTerminal nt = new NonTerminal("S" + n++);
                    this.insertSubMachineCall(grammar, rule, callerIndex, targetIndex, nt);
                    ProductionRule newRule = this.createNewRule(grammar, nt, cycle);

                    // Cria uma transição epsilon pra essa submaquina
                    ProductionRule epsilonRule = new ProductionRule(nt);
                    epsilonRule.add(new Epsilon());
                    grammar.addRule(epsilonRule);

                    // Recursivamente VerificaCaminhoMínimo em Si
                    n = findNewCycles(sm, visitedStates, n, grammar, cycle, newRule);
                }
            }
        } while (!visitedTransition.containsAll(transFrom) && !cycle.isEmpty());
        return n;
    }

    public ProductionRule createNewRule(ContextFreeGrammar grammar, NonTerminal generator, List<Transition> path) {
        ProductionRule rule = new ProductionRule(generator);
        if (path.isEmpty()) {
            rule.add(new Epsilon());
        } else {
            for (Transition t : path) {
                String terminalName = t.getConditions().get(0);
                if (!grammar.hasTerminal(terminalName)) {
                    Terminal terminal = new Terminal(terminalName);
                    grammar.addTerminal(terminal);
                    rule.add(terminal);
                } else {
                    rule.add(grammar.getTerminal(terminalName));
                }
            }
            grammar.addRule(rule);
        }
        return rule;
    }

    /**
     * Insert newE element after prev element in rule
     * 
     * @param rule
     * @param nt
     */
    protected void insertSubMachineCall(ContextFreeGrammar grammar, ProductionRule rule, int prev, int next,
            ProductionElement newE) {
        if (prev == next) {
            rule.add(prev, newE);
        } else {
            ProductionRule newRule = new ProductionRule(rule.getGenerator());
            List<ProductionElement> products = rule.getProducts();
            int i = 0;
            while (i < products.size()) {
                if (i < prev || i >= next) {
                    newRule.add(products.get(i));
                } else if (i == prev) {
                    newRule.add(newE);
                } // if prev < i < next -> nothing
                i++;
            }
            grammar.addRule(newRule);
        }
    }

    /**
     * 
     * @param grammar
     * @param cycle
     * @return Rule or null if not found
     */
    private ProductionRule getRule(ContextFreeGrammar grammar, List<Transition> cycle) {

        ProductionRule result = null;

        for (ProductionRule rule : grammar.getRules()) {

            if (!rule.getGenerator().equals(grammar.getStartSymbol())) {
                int i = 0;
                boolean found = true;
                for (ProductionElement element : rule.getProducts()) {
                    if (i < cycle.size()) {
                        String cond = cycle.get(i).getConditions().get(0);
                        if (element.getName().equals(cond)) {
                            i++;
                        } else {
                            found = false;
                            break;
                        }
                    } else {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    result = rule;
                    break;
                }
            }
        }

        return result;
    }

    /**
     * Calculates distances from s to every state t in sm, with t nearer to an accept state than s;
     * 
     * @param sm
     * @param s
     * @return
     */
    protected Map<State, Integer> calculateDistances(StateMachine sm, State s) {

        Queue<State> queue = new LinkedList<State>();
        Map<State, Integer> dist = new HashMap<State, Integer>();

        // Initialize distance map
        for (State st : sm.getAllStates()) {
            dist.put(st, -1);
        }
        dist.put(s, 0);
        queue.offer(s);

        boolean minimalDistanceReached = false;

        while (!queue.isEmpty()) {
            State ref = queue.remove();
            // Loop nos vizinhos

            for (Transition t : ref.getAllTransitions()) {
                State adj = t.getStateTo();

                if (dist.get(adj) == -1) { // Not visited yet
                    dist.put(adj, dist.get(ref) + 1);
                    if (adj.isAcceptState()) {
                        minimalDistanceReached = true;
                    }
                    if (!minimalDistanceReached) {
                        queue.offer(adj);
                    }
                }
            }
        }

        return dist;

    }

    protected ArrayList<List<State>> segmentDist(State finalState, Map<State, Integer> dist) {
        int minDist = dist.get(finalState);

        System.out.println("Min dist = " + minDist);

        // Separando o mapa de distancias em listas por valor.
        // Lista de distancia 1, lista de distancia 2, etc.
        ArrayList<List<State>> distSegmented = new ArrayList<List<State>>();

        int aux = 0;

        while (aux <= minDist) {
            ArrayList<State> distI = new ArrayList<State>();

            Iterator<Entry<State, Integer>> it = dist.entrySet().iterator();

            while (it.hasNext()) {
                Entry<State, Integer> entry = it.next();
                if (entry.getValue() == aux) {
                    distI.add(entry.getKey());
                    it.remove(); // Remove do mapa também.
                }
            }
            distSegmented.add(distI);
            aux++;
        }
        System.out.println("Lista segmentada: " + distSegmented);

        return distSegmented;
    }

    protected List<List<Transition>> findMinPaths(StateMachine sm, State initialState, State finalState) {

        Map<State, Integer> dist = this.calculateDistances(sm, initialState);
        int minDist = dist.get(finalState);
        ArrayList<List<State>> distSegmented = segmentDist(finalState, dist);

        List<List<Transition>> minPaths = new ArrayList<List<Transition>>();

        if (minDist > 0) {

            int aux = minDist - 1;

            for (State st : distSegmented.get(aux)) {
                ArrayList<Transition> newPath = new ArrayList<Transition>();
                newPath.add(st.getTransitionTo(finalState));
                minPaths.add(newPath);
            }

            aux = aux - 1;
            while (aux >= 0) {

                List<List<Transition>> minPathsCopy = new ArrayList<List<Transition>>(minPaths);

                for (List<Transition> path : minPathsCopy) {
                    State last = path.get(0).getStateFrom();
                    for (State st : distSegmented.get(aux)) {
                        Transition t = st.getTransitionTo(last);
                        if (t != null) {
                            List<Transition> rightPath = path;
                            if (path.size() >= minDist - aux) {
                                // copy path
                                ArrayList<Transition> anotherPath = new ArrayList<Transition>(path);
                                anotherPath.remove(0);
                                minPaths.add(anotherPath);
                                rightPath = anotherPath;
                            }
                            rightPath.add(0, t);
                        }
                    }
                }
                aux--;
            }
        } else {
            for(Transition t : initialState.getAllTransitions()) {
                if (t.getStateTo().equals(initialState)) {
                    List<Transition> minPath = new ArrayList<Transition>();
                    minPath.add(t);
                    minPaths.add(minPath);
                }
            }
        }
        return minPaths;
    }

    /**
     * Finds shortest cycle starting and ending at any states given (not necessarily the same) and not passing through
     * any forbidden states
     * 
     * @param sm
     * @param initial
     * @return
     */
    protected List<Transition> findMinimalCycle(StateMachine sm, List<State> states, List<State> forbidden) {

        Map<State, State> parent = new HashMap<State, State>();
        Queue<State> queue = new LinkedList<State>();
        LinkedList<Transition> cycle = new LinkedList<Transition>();
        Set<State> visited = new HashSet<State>();

        // Initialize
        for (State st : sm.getAllStates()) {
            parent.put(st, null);
        }

        queue.addAll(states);
        queue.removeAll(forbidden);
        visited.addAll(states);
        visited.addAll(forbidden);

        boolean found = false;

        while (!queue.isEmpty() && !found) {
            State ref = queue.remove();

            // Loop nos vizinhos
            for (Transition t : ref.getAllTransitions()) {
                State adj = t.getStateTo();
                if (!visitedTransition.contains(t)) {

                    if ((states.contains(adj) && !states.contains(ref) && !forbidden.contains(adj))
                            || (states.contains(adj) && adj.equals(ref))) { // Achou ciclo
                        cycle.addFirst(t);
                        State aux = ref;
                        while (!states.contains(aux)) {
                            cycle.addFirst(parent.get(aux).getTransitionTo(aux));
                            aux = parent.get(aux);
                        }
                        found = true;
                        break;
                    } else if (!visited.contains(adj)) { // Not visited yet
                        queue.offer(adj);
                        parent.put(adj, ref);
                        visited.add(adj);
                    }
                }
            }
        }
        return cycle;
    }
}
